
import java.util.ArrayList;
import java.util.List;

public class RestoreIPAddresses0103_93 {
    List<String> result = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    public List<String> restoreIpAddresses(String s) {
        backTracking(s,0,0);
        return result;
    }

    // ipCount表示path中ip段的数量
    private void backTracking(String s, int startIndex, int ipCount) {
        // 如果startIndex等于s的长度并且ip段的数量是4，则加入结果集，并返回
        if(ipCount == 4 && startIndex == s.length()){
            result.add(path.toString());
            return;
        }
        // 如果startIndex等于s的长度但是ip段的数量不为4，或者ip段的数量为4但是startIndex小于s的长度，则直接返回
        if(ipCount == 4 || startIndex == s.length()) return;

        // 剪枝：ip段的长度最大是3，并且ip段处于[0,255]
        for (int i = startIndex; i < s.length() && i-startIndex < 3
                && Integer.parseInt(s.substring(startIndex,i+1)) >= 0
                && Integer.parseInt(s.substring(startIndex,i+1)) <= 255
                ; i++) {

            // 如果ip段的长度大于1，并且第一位为0的话，continue
            if(i-startIndex > 0 && s.charAt(startIndex) == '0') continue;

            path.append(s.substring(startIndex,i+1));
            // 当path里的网段数量小于3时，才会加点；如果等于3，说明已经有3段了，最后一段不需要再加点
            if(ipCount < 3) path.append(".");
            ipCount++;

            backTracking(s,i+1,ipCount);

            ipCount--;
            // 删除当前path最后一个网段，注意考虑点的数量的问题
            path.delete(startIndex+ipCount, i+ipCount+2);
        }
    }

//    private boolean isValid(String s, int startIndex, int end){
//        if(startIndex> end) return false;
//
//        if(s.charAt(startIndex) == '0' && startIndex != end) return  false;
//
//        int num = 0;
//        for (int i = startIndex; i < end+1; i++) {
//            int digit =  s.charAt(i) - '0';
//            num = num*10 + digit;
//            if(num>255) return false;
//        }
//        return true;
//    }


}
